package com.mj.Tree;


import com.mj.linkedlist.tools.Times;
import com.mj.printer.BinaryTrees;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @Author: LDeng
 * @Date: 2021-02-26 15:58
 */
public class Main {


    static void testBinarySearchTree() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 3, 12, 1};
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.print(bst);
        System.out.println("\n");
        bst.remove1(7);
        BinaryTrees.print(bst);
    }

    static void testAVLTree() {
        Integer data[] = new Integer[]{19, 16, 15, 9, 10, 7, 1, 5, 13, 14, 12, 4, 20};
        AVLTree<Integer> avlTree = new AVLTree<>();
        for (int i = 0; i < data.length; i++) {
            avlTree.add(data[i]);
            System.out.println("【增加的元素为：" + data[i] + "】");
            BinaryTrees.print(avlTree);
            System.out.println("\n" + "-----------------------------------");
        }

        BinaryTrees.print(avlTree);
        System.out.println("\n");
        avlTree.remove1(20);
        avlTree.remove1(19);
        avlTree.remove1(15);
        avlTree.remove1(16);
        BinaryTrees.print(avlTree);
    }

    static void testPeformance() {
        List<Integer> data = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            data.add((int) (Math.random() * 100000));
        }
        for (int i = 0; i < 100000; i++) {
            data.contains(i);
        }
//        for(int i=999999;i>0;i--){
//            data.remove(i);
//        }

//        BinarySearchTree<Integer> bst=new BinarySearchTree<>();
//        for(int i=0;i< 1000000;i++){
//            bst.add((int) (Math.random()*1000000));
//        }
//        for(int i=0;i< bst.size();i++){
//            bst.contains(i);
//        }
//        for(int i=999999;i>0;i--){
//            bst.remove(i);
//        }

//        AVLTree<Integer> avlTree=new AVLTree<>();
//        for(int i=0;i< 1000000;i++){
//            avlTree.add((int) (Math.random()*1000000));
//        }
//        for(int i=0;i< avlTree.size();i++){
//            avlTree.contains(i);
//        }
//        for(int i=999999;i>0;i--){
//            avlTree.remove(i);
//        }

    }

    static void testRBTreeAdd() {
        Integer data[] = new Integer[]{
                55,87,56,74,96,22,62,20,70,68,90,50
        };
        RBTree<Integer> rbTree = new RBTree<>();
        for (int i = 0; i < data.length; i++) {
            rbTree.add(data[i]);
        }
        System.out.println("\n");
        BinaryTrees.print(rbTree);
    }


    static void testRBTreeRemove() {
        Integer data[] = new Integer[]{
                55,87,56,74,96,22,62,20,70,68,90,50
        };
        RBTree<Integer> rbTree = new RBTree<>();
        for (int i = 0; i < data.length; i++) {
            rbTree.add(data[i]);
        }


        BinaryTrees.print(rbTree);
        System.out.println("\n");
        System.out.println("^^^^^^^^删除前的红黑树^^^^^^^^^");

        for (int i = 0; i < data.length; i++) {
            rbTree.remove(data[i]);
            System.out.println("\n"+"-----------------------------------");
            System.out.println("删除的元素是【"+data[i]+"】");
            BinaryTrees.print(rbTree);
        }
    }


    public static void main(String[] args) {
        //testBinarySearchTree();
        //testAVLTree();
//        Times.check("testPeformance", new Times.Task() {
//            @Override
//            public void execute() {
//                testPeformance();
//            }
//        });
//        testRBTreeAdd();
        testRBTreeRemove();
    }
}
